package cn.xiaolang.function.data_structure;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 栈排序
 * <p>
 * 栈排序。 编写程序，对栈进行排序使最小元素位于栈顶。最多只能使用一个其他的临时栈存放数据，但不得将元素复制到别的数据结构（如数组）中。
 * 该栈支持如下操作：push、pop、peek 和 isEmpty。当栈为空时，peek返回 -1。
 * <p>
 * 示例1:
 * <p>
 * 输入：
 * ["SortedStack", "push", "push", "peek", "pop", "peek"]
 * [[], [1], [2], [], [], []]
 * 输出：
 * [null,null,null,1,null,2]
 * 示例2:
 * <p>
 * 输入：
 * ["SortedStack", "pop", "pop", "push", "pop", "isEmpty"]
 * [[], [], [], [1], [], []]
 * 输出：
 * [null,null,null,null,null,true]
 * 说明:
 * <p>
 * 栈中的元素数目在[0, 5000]范围内。
 */
public class No14sortStack {

    public static void main(String[] args) {
        SortedStack obj = new SortedStack();
        obj.push(3);
        obj.push(1);
        obj.push(2);
        obj.push(4);
        // 1
        System.out.println(obj.peek());
        obj.pop();
        // 2
        System.out.println(obj.peek());
        obj.pop();
        // 3
        System.out.println(obj.peek());
        obj.pop();
        // 4
        System.out.println(obj.peek());
        obj.pop();
        // -1
        System.out.println(obj.peek());
    }

    /**
     * 执行用时：113 ms, 在所有 Java 提交中击败了75.80%的用户
     * 内存消耗：43.3 MB, 在所有 Java 提交中击败了5.06%的用户
     */
    static class SortedStack2 {

        private final Deque<Integer> stk;

        public SortedStack2() {
            stk = new ArrayDeque<>();
        }

        public void push(int val) {
            Integer minVal = stk.peek();
            // 为空，或者val值更小直接push
            if (isEmpty() || minVal == null || val <= minVal) {
                stk.push(val);
                return;
            }
            // val值大于栈顶，则取出栈顶temp，再递归push，同时把temp再放入栈
            int temp = stk.pop();
            push(val);
            stk.push(temp);
        }

        public void pop() {
            if (!isEmpty()) stk.pop();
        }

        public int peek() {
            return stk.isEmpty() ? -1 : stk.peek();
        }

        public boolean isEmpty() {
            return stk.isEmpty();
        }
    }


    static class StackNode {
        private final Integer val;
        private StackNode next;

        public StackNode(Integer val, StackNode next) {
            this.val = val;
            this.next = next;
        }
    }

    /**
     * 结果：
     * 执行用时：16 ms, 在所有 Java 提交中击败了87.08%的用户
     * 内存消耗：41.1 MB, 在所有 Java 提交中击败了90.35%的用户
     *
     * 思路：
     * 1. push元素的时候排序
     * <p>
     * beforeNode
     * <p>
     * node1[val1,next2] ----node2[val2,next2]-----node3[val3,next3]------
     * 1. if newVal<=val1 newNode[newVal,node1]
     * 2. if newVal>val1 找node2比较：beforeNode = node1
     * 2.1 newVal<=val2 beforeNode.next=newNode[newVal,node2]
     * 2.2 newVal>val2 找node3, beforeNode = node2
     */
    static class SortedStack {

        private StackNode head;

        public SortedStack() {

        }

        public void push(int val) {
            if (isEmpty()) {
                head = new StackNode(val, null);
            } else {
                // 1.如果push的值小于最小值节点head，直接创建一个新node指向当前节点
                if (val <= head.val) {
                    head = new StackNode(val, head);
                    return;
                }
                // 2.当前只有一个节点,当前节点指向创建一个新node
                if (head.next == null) {
                    head.next = new StackNode(val, null);
                    return;
                }
                StackNode beforeGreaterValNode = head;
                StackNode greaterValNode = head.next;
                // 3. push的值大于下一个节点的值，则再找下一个节点的next
                while (greaterValNode != null && val > greaterValNode.val) {
                    beforeGreaterValNode = greaterValNode;
                    greaterValNode = beforeGreaterValNode.next;
                }
                // 4. 找节点值大于push值的节点greaterValNode，没找到或者找到最后一个，创建一个新node指向greaterValNode
                if (greaterValNode == null || greaterValNode.next == null) {
                    beforeGreaterValNode.next = new StackNode(val, greaterValNode);
                } else {
                    // 5. 找节点值大于push值的节点greaterValNode，非最后一个，修改上一个节点beforeGreaterValNode的next指向新节点，
                    // 新节点的next指向上一个节点beforeGreaterValNode的next
                    beforeGreaterValNode.next = new StackNode(val, beforeGreaterValNode.next);
                }
            }
        }

        public void pop() {
            if (!isEmpty()) head = head.next;
        }

        public int peek() {
            return isEmpty() ? -1 : head.val;
        }

        public boolean isEmpty() {
            return head == null;
        }
    }

}
